package algorithm;

/**
 * 前缀不包括最后一个字符
 * 后缀不包括第一个字符
 *
 * 利用最长前缀和最长后缀实现
 *
 *
 * "abab cwc ababq"
 */
public class KMP {


    public static int getIndexOf(String s, String t) {
        if (s == null || t == null || s.length()<1 || t.length()<1 || s.length() < t.length()) {
            return -1;
        }
        char[] source=s.toCharArray();
        char[] target=t.toCharArray();
        int i1 = 0;
        int i2 = 0;
        int[] next = getNextArray(t.toCharArray());
        while (i1 < source.length && i2 < target.length) {
            if (source[i1] == target[i2]) {
                i1++;
                i2++;
            } else if (next[i2] == -1) {
                i1++;
            } else {
                i2 = next[i2];
            }
        }
        return i2 == target.length? i1-i2: -1;
    }
    /**
     * 构建next数组
     * @param string
     * @return
     */
    public static int[] getNextArray(char[] string) {
        if (string.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[string.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < string.length) {
            if (string[i-1] == string[cn]) {
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }
    public static void main(String[] args) {
        System.out.printf(getIndexOf("abcsdsadnsoa", "adnso") + "");
    }
}
